A pipelined processor that executes pipelined instruction codes fetches instruction codes one after another to cause the stages of the pipeline to constantly operate in order to prevent decrease in the efficiency of the processing of the instruction codes.
In the pipelined processor, the behavior of branch instructions is predicted and instruction codes are speculatively fetched to maintain constant pipeline operation in order to prevent decrease in the efficiency of execution of instruction codes.
In order to maintain constant pipeline operation, a branch prediction scheme with high prediction accuracy needs to be used.
A branch prediction scheme is used that predicts a prediction target and direction for a branch instruction code on the basis of a history recording the targets and directions of past branches, with the aim of improving the accuracy of branch prediction.
The history that records branch targets and directions that are effective for branch prediction depends on parameters such as the number of branch instructions contained in an application program, branch direction bias of each individual branch instruction, and the locations of branch instructions on a memory.
This means that given that the amount of history that may be stored is unchangeable, the accuracy of branch prediction may not be improved unless history entries that are effective for branch prediction are preferentially stored. In other words, the nature of application programs described above needs to be taken into consideration to select history entries of the past that are effective for branch prediction in order to increase the accuracy of branch prediction.
If history of every past branch were recorded, the history entries would occupy a larger memory space. Therefore many approaches to improving predication accuracy with a limited amount of history of the past branches have been proposed (See for example Japanese Laid-Open Patent Publication No. 11-96005).
However, there are many branch instructions that do not have branch direction bias and some regularity beside branch instructions that have branch direction bias and some regularity. It is therefore not easy to select history entries of branch instructions that are worth storing.